PC-Blue - MS DOS Public Domain Library/PC-Blue MS-DOS Public Domain Library - NYACC.iso/vol270/hsort.c

C/C++ Source or Header | 1986-12-16 | 5.1 KB | 179 lines

/*    hsort - general purpose heapsort

    Author...
        Copyright (c) 1985  James R. Van Zandt

        All rights reserved.
        This program may be copied for personal, non-profit use only.

        Based on algorithms by Jon Bentley [Communications of the ACM v
        28 n 3 p 245 (Mar 85) and v 28 n 5 p 456 (May 85)], and the
        sort interface routines by Allen I.  Holub [Dr.  Dobb's Journal
        #102 (Apr 85)].

    Usage...

        Including a #define for DEBUG will make this file a stand-alone
        program which sorts argv and prints the result, along with the
        heap at the intermediate stages.  This is instructive if you
        want to see how the heap sort works.  #defining DEBUG2 will
        also print results of comparisons.

    Notes...
        This routine sorts N objects in worst-case time proportional to
        N*log(N).  The heapsort was discovered by J.  W.  J.  Williams
        [Communications of the ACM v 7 p 347-348 (1964)] and is
        discussed by D.  E.  Knuth [The Art of Computer Programming,
        Volume 3: Sorting and Searching, Addison-Wesley, Reading,
        Mass., 1973, section 5.2.3].

        This algorithm depends on a portion of an array having the
        "heap" property.  The array X has the property heap[L,U] if:

            for all      L, i, and U
            such that    2L <= i <= U
            we have      X[i div 2] <= X[i]

        sift_down enlarges the heap: It accepts an array with heap[L+1,U]
        and returns an array with heap[L,U].
*/

typedef int (*PFI)();        /* pointer to a function returning int    */
static PFI Comp;            /* pointer to comparison routine        */
static int Width;            /* width of an object in bytes            */
static char *Base;            /* pointer to element [-1] of array        */
static char *a, *b, tmp;    /* temporaries for exchanges            */

#ifdef DEBUG
int Exchanges=0, Comparisons=0;
#endif

/*--------------------------------------------------------------------------*/
int argvcmp(s1p,s2p) char **s1p,**s2p;
{
    /*    Comparison routine for sorting an argv like list of pointers to
        strings.  Just remove one level of indirection and call strcmp
        to do the comparison                                                */

#ifdef DEBUG
    Comparisons++;
#endif
#ifdef DEBUG2
    register int rval;
    rval=strcmp(*s1p,*s2p);
    printf("   argvcmp(<%s><%s>) = %d\n",*s1p,*s2p,rval);
    return (rval);
#else
    return (strcmp(*s1p,*s2p));
#endif
}

hsort(base,nel,width,compare)
char *base;
int    nel,width;
int    (*compare)();
{
static int i,j,n,stop;
    /*    Perform a heap sort on an array starting at base.  The array is
        nel elements large and width is the size of a single element in
        bytes.  Compare is a pointer to a comparison routine which will
        be passed pointers to two elements of the array.  It should
        return a negative number if the left-most argument is less than
        the rightmost, 0 if the two arguments are equal, a positive
        number if the left argument is greater than the right.  (That
        is, it acts like a "subtract" operator.) If compare is 0 then
        the default comparison routine, argvcmp (which sorts an
        argv-like array of pointers to strings), is used.                    */

#ifdef DEBUG
    static int ii;
    printf("Sorting %d element array of %d byte elements at 0x%x\n",
        nel,width,base);
    printf("Comparison routine at 0x%x. Unsorted list:\n",compare);
    ptext(1,nel,base);
    for ( ii=1 ; ii<=nel ; ii++ ) printf("[%d]     ",ii);
    printf("\n");
#endif
    Width=width;
    Comp=(compare==(PFI)0) ? &argvcmp : compare ;
    n=nel*Width;
    Base=base-Width;
    for (i=(n/Width/2)*Width; i>=Width; i-=Width) sift_down(i,n);
#ifdef DEBUG
    printf("Heap constructed\n");
    for ( ii=1 ; ii<=nel ; ii++ ) printf("[%d]     ",ii);
    printf("\n");
#endif
    stop=Width+Width;
    for (i=n; i>=stop; )
        {for (b=base, a=Base+i, j=Width ; j-- ; )
            {tmp = *b; *b++ = *a; *a++ = tmp;
            }
#ifdef DEBUG
        Exchanges++;
#endif
        sift_down(Width,i-=Width);
        }

#ifdef DEBUG
    printf("\nSort complete, list is:\n");
    ptext(1,nel,base);
    printf("%d comparisons and %d exchanges were performed \n",
    Comparisons,Exchanges);
#endif
}

/*---------------------------------------------------------------------------*/
static sift_down(L,U) int L,U;
/*    pre: heap(L+1,U)        */
{    int c,count;

#ifdef DEBUG
    int i1;
    i1=L;
#endif
    while(1)
        {c=L+L;
        if(c>U) break;
        if( (c+Width <= U) && ((*Comp)(Base+c+Width,Base+c)>0) ) c+= Width;
        if ((*Comp)(Base+L,Base+c)>=0) break;
        for(b=Base+L,a=Base+c,count=Width; count-- ; )
            {tmp=*b; *b++ = *a; *a++ = tmp;
            }
#ifdef DEBUG
        Exchanges++;
#endif
        L=c;
        }
#ifdef DEBUG
    ptext(i1/2,U/2,Base+Width);
#endif
/*    post: heap(L,U)            */
}

/*--------------------------------------------------------------------------*/
/*        Test routine for hsort, compiled if DEBUG is #defined                */

#ifdef DEBUG
static ptext( start, end, argv)
int start,end;
char **argv;
{
    /*    Print out argv, one element per line    */

    register int i;
    for (i=1; i<start; i++) {printf("        "); argv++;}
    for ( i=start ; i<=end ; i++ ) printf("%-8s",*argv++);
    printf("\n");
}

main(argc,argv) int argc; char **argv;
{
    /*    Test routine for hsort.  Sorts argv (less the first element).    */

    hsort(++argv,--argc,sizeof(PFI),0);
}

#endif